package leetcode.editor.cn;

//请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。 
//
// 
// get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 
// put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效
//。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。 
// 
//
// 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 
//
// 
//
// 进阶： 
//你是否可以在 O(1) 时间复杂度内执行两项操作？ 
//
// 
//
// 示例： 
//
// LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1);       // 返回 1
//cache.put(3, 3);    // 去除 key 2
//cache.get(2);       // 返回 -1 (未找到key 2)
//cache.get(3);       // 返回 3
//cache.put(4, 4);    // 去除 key 1
//cache.get(1);       // 返回 -1 (未找到 key 1)
//cache.get(3);       // 返回 3
//cache.get(4);       // 返回 4 
// Related Topics 设计

import java.util.HashMap;
import java.util.LinkedHashSet;

public class LfuCache{
    public static void main(String[] args) {
//        LFUCache cache = new LFUCache(2);
//        cache.put(1,1);
//        cache.put(2,2);
//        cache.get(1);
//        cache.put(3,3);
//        cache.get(2);
//        cache.get(3);
//        cache.put(4,4);
//        System.out.println(cache.get(1));
//        cache.get(3);

    }

//leetcode submit region begin(Prohibit modification and deletion)
class LFUCache {

    class Node {
         int key;
         int val;
         int freq = 1;
         Node(){}
         Node(int key, int val) {
             this.key = key;
             this.val = val;
         }
    }

    HashMap<Integer, Node> map;
    //使用次数 : 链表
    HashMap<Integer, LinkedHashSet<Node>> cache;
    int min;
    int capacity;
    int size;


    public LFUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(2);
        cache = new HashMap<>();
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null) return -1;
        freqInc(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(capacity == 0) return;
        Node node = map.get(key);
        if(node == null){
            //先判断是否已经空间满了
            if(size == capacity){
                Node delNode = removeNode();
                map.remove(delNode.key);
                size--;
            }
            node = new Node(key,value);
            map.put(key,node);
            size++;
            addNode(node);
        }else{
            node.val = value;
            freqInc(node);
        }
    }

    void freqInc(Node node){
        int req = node.freq;
        LinkedHashSet<Node> set = cache.get(req);
        if(set != null) {
            set.remove(node);
            if (req == min && set.size() == 0) {
                min = req + 1;
            }
        }
        LinkedHashSet<Node> addSet = cache.get(req+1);
        if(addSet == null){
            addSet = new LinkedHashSet<>();
            cache.put(req +1, addSet);
        }
        node.freq ++;
        addSet.add(node);
    }

    void addNode(Node node){
        LinkedHashSet<Node> set = cache.get(1);
        if(set == null){
            set = new LinkedHashSet();
            cache.put(1,set);
        }
        set.add(node);
        min = 1;
    }

    Node removeNode(){
        LinkedHashSet<Node> set = cache.get(min);
        Node node = set.iterator().next();
        set.remove(node);
        return node;
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}